package com.leetcode.partition12;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/10/29 14:18
 */
public class LC1155掷骰子的N种方法 {

    private static final int MOD = 1000000007;

    public static int numRollsToTarget(int d, int f, int target) {
        if (d > target) return 0;
        return dynamicProgramming(d, f, target);
    }

    public static void main(String[] args) {
        System.out.println(numRollsToTarget(3, 6, 4));
    }

    private static int dynamicProgramming(int d, int f, int target) {
        //dp[i][j]：i个骰子总和有j的数量
        int[][] dp = new int[d + 1][target + 1];
        //初始化：n个骰子出现n的情况只有一种，那就是全为1；一个骰子有f个面，则骰出j(j属于f)的只有j朝上一种情况
        for (int i = 1; i <= d; i++) dp[i][i] = 1;
        for (int j = 1; j <= f && j <= target; j++) dp[1][j] = 1;
        for (int i = 2; i <= d; i++) {
            //n个骰子的最小就是n个都是1向上，最小值为n
            for (int j = i + 1; j <= target; j++) {
                for (int k = 1; k <= f && k < j; k++) {
                    //枚举每个骰子的点数k，根据上一层的计算结果得到方案数
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
                }
            }
        }
        Arrays.stream(dp).forEach(val -> System.out.println(Arrays.toString(val)));
        return dp[d][target];
    }
}
